package org.example;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class MyRecurCase {

    public List<Integer> MyQuickSort(List<Integer> lst) {
        if (lst != null && !lst.isEmpty() && lst.size() > 0) {
            if(lst.size() == 1) {
                return lst;
            } else {
                Integer i = lst.get(0);
                List<Integer> rs = new ArrayList<>();
                List<Integer> lst1 = new ArrayList<>();
                List<Integer> lst2 = new ArrayList<>();
                for (int index = 1; index < lst.size(); index++) {
                    if (lst.get(index) < i) {
                        lst1.add(lst.get(index));
                    } else {
                        lst2.add(lst.get(index));
                    }
                }

                if (lst1.size() > 0) {
                    List<Integer> rs1 = MyQuickSort(lst1);
                    if (rs1 != null && rs1.size() > 0) {
                        rs.addAll(rs1);
                    }
                }
                rs.add(i);
                if (lst2.size() > 0) {
                    List<Integer> rs2 = MyQuickSort(lst2);
                    if (rs2 != null && rs2.size() > 0) {
                        rs.addAll(rs2);
                    }
                }
                return rs;
            }
        }
        return null;
    }

    @Test
    public void test1(){
        List<Integer> lst = new ArrayList<>();
        lst.add(5);
        lst.add(3);
        lst.add(9);
        lst.add(6);
        lst.add(2);
        List<Integer> rs = MyQuickSort(lst);
        System.out.println(rs);
    }

    @Test
    public void test2(){
        List<Integer> lst = new ArrayList<>();
        lst.add(5);
        lst.add(3);
        lst.add(9);
        lst.add(6);
        lst.add(2);
        MyRecur myRecur = new MyRecur();
        myRecur.Initi(lst);
        myRecur.PushStack();
        List<MyParams> stack = myRecur.getStack();
        System.out.println(stack);
    }
}














































